/******************************************************************************************
 * Data Structures in C++
 * ISBN: 7-302-33064-6 & 7-302-33065-3 & 7-302-29652-2 & 7-302-26883-3
 * Junhui DENG, deng@tsinghua.edu.cn
 * Computer Science & Technology, Tsinghua University
 * Copyright (c) 2006-2013. All rights reserved.
 ******************************************************************************************/

#pragma once

template <typename Tv, typename Te> 
void Graph<Tv, Te>::dfs(int s) { 
   reset(); int clock = 0; int v = s; 
   do 
      if (UNDISCOVERED == status(v)) 
         DFS(v, clock); 
   while (s != (v = (++v % n))); 
}

template <typename Tv, typename Te> 
void Graph<Tv, Te>::DFS(int v, int& clock) { 
   dTime(v) = ++clock; status(v) = DISCOVERED; 
   for (int u = firstNbr(v); -1 < u; u = nextNbr(v, u)) 
      switch (status(u)) { 
         case UNDISCOVERED: 
            status(v, u) = TREE; parent(u) = v; DFS(u, clock); break;
         case DISCOVERED: 
            status(v, u) = BACKWARD; break;
         default: 
            status(v, u) = (dTime(v) < dTime(u)) ? FORWARD : CROSS; break;
      }
   status(v) = VISITED; fTime(v) = ++clock; 
}
